//#define  _CRT_SECURE_NO_WARNINGS
//#include <iostream>
//using namespace std;
//
//int main()
//{
//	int m, n;
//	cin >> m >> n;
//	int ret = m;
//	while (--n)
//	{
//		ret *= (m - 1);
//		ret %= 109;
//	}
//	cout << ret << endl;
//}